package club.xiaojiawei.strings;

/**
 * @author 肖嘉威
 * @version 1.0
 * @date 6/22/22 2:09 PM
 * @question 925. 长按键入
 * @description 你的朋友正在使用键盘输入他的名字 name。偶尔，在键入字符 c 时，按键可能会被长按，而字符可能被输入 1 次或多次。
 * 你将会检查键盘输入的字符 typed。如果它对应的可能是你的朋友的名字（其中一些字符可能被长按），那么就返回 True。
 */
public class IsLongPressedName925 {

    public static void main(String[] args) {
        IsLongPressedName925 test = new IsLongPressedName925();
        boolean result = test.isLongPressedName("alexd", "ale");
        System.out.println(result);
    }

    /**
     * 双指针
     * 时间复杂度：O(N+M)
     * 空间复杂度：O(1)
     * @param name
     * @param typed
     * @return
     */
    public boolean isLongPressedName(String name, String typed) {
        int count;
        char temp;
        int j = 0;
        for (int i = 0; i < name.length(); i++) {
            count = 1;
            temp = name.charAt(i);
            while (i + 1 < name.length() && name.charAt(i + 1) == temp){
                i++;
                count++;
            }
            for (;j < typed.length(); j++){
                if (temp == typed.charAt(j)){
                    count--;
                }else {
                    break;
                }
            }
            if (count > 0 ){
                return false;
            }
        }
        return j == typed.length();
    }

    /**
     * 官方-双指针
     * 时间复杂度：O(N+M)
     * 空间复杂度：O(1)
     * @param name
     * @param typed
     * @return
     */
    public boolean isLongPressedName2(String name, String typed) {
        int i = 0, j = 0;
        while (j < typed.length()) {
            if (i < name.length() && name.charAt(i) == typed.charAt(j)) {
                i++;
                j++;
            } else if (j > 0 && typed.charAt(j) == typed.charAt(j - 1)) {
                j++;
            } else {
                return false;
            }
        }
        return i == name.length();
    }

}
